Exercise 7 (Homework 5).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
coRE,
symmetric difference)
\mathbf{R}, \mathbf{RE}, \mathbf{coRE}, and symmetric difference
Given two sets A and B recall that the symmetric difference of A and B is A\Delta B=(A\cup B)\setminus (A\cap B). Assume that A\Delta B\in \mathbf{R}.
- Does A\in \mathbf{R} imply that B\in \mathbf{R}?
- Does A\in \mathbf{RE} imply that B\in \mathbf{RE}?
- Does A\in \mathbf{coRE} imply that B\in \mathbf{coRE}?